package com.zjsru.plan2025.oneday;

/**
 * 1061. 按字典序排列最小的等效字符串
 *
 * @Author: cookLee
 * @Date: 2025-06-05
 */
public class SmallestEquivalentString {

    /**
     * 主
     * \
     * 输入：s1 = "parker", s2 = "morris", baseStr = "parser"
     * 输出："makkek"
     * 解释：根据 A 和 B 中的等价信息，我们可以将这些字符分为 [m,p], [a,o], [k,r,s], [e,i] 共 4 组。每组中的字符都是等价的，并按字典序排列。所以答案是 "makkek"。
     * \
     * 输入：s1 = "hello", s2 = "world", baseStr = "hold"
     * 输出："hdld"
     * 解释：根据 A 和 B 中的等价信息，我们可以将这些字符分为 [h,w], [d,e,o], [l,r] 共 3 组。所以只有 S 中的第二个字符 'o' 变成 'd'，最后答案为 "hdld"。
     * \
     *
     * @param args args
     */
    public static void main(String[] args) {
        SmallestEquivalentString smallestEquivalentString = new SmallestEquivalentString();
        System.out.println(smallestEquivalentString.smallestEquivalentString("parker", "morris", "parser"));
    }

    private int[] parent;

    public SmallestEquivalentString() {
        this.parent = new int[26];
        for (int i = 0; i < 26; i++) {
            this.parent[i] = i;
        }
    }

    public int find(int x) {
        //因传递性寻找最小值
        if (x != this.parent[x]) {
            this.parent[x] = this.find(this.parent[x]);
        }
        return this.parent[x];
    }

    public void union(int x, int y) {
        int px = this.find(x);
        int py = this.find(y);
        if (px == py) {
            return;
        }
        if (px > py) {
            int temp = px;
            px = py;
            py = temp;
        }
        this.parent[py] = px;
    }

    /**
     * 并查集
     *
     * @param s1      s1
     * @param s2      s2
     * @param baseStr 基础力量
     * @return {@link String}
     */
    public String smallestEquivalentString(String s1, String s2, String baseStr) {
        SmallestEquivalentString smallestEquivalentString = new SmallestEquivalentString();
        for (int i = 0; i < s1.length(); i++) {
            smallestEquivalentString.union(s1.charAt(i) - 'a', s2.charAt(i) - 'a');
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < baseStr.length(); i++) {
            sb.append((char) (smallestEquivalentString.find(baseStr.charAt(i) - 'a') + 'a'));
        }
        return sb.toString();
    }
}
